CF464D World of Darkraft - 2

首先明确一点,所有装备的期望相同,只需求出任意一种后答案乘 kk 即可。

dp[i][j]dp[i][j] 表示还需要打 ii 只怪,装备等级为 jj 的金币数量期望。

那么有三种情况:

阅读全文 »

CF398B Painting The Wall

先考虑所有格子均未涂色的情况。

因为格子的涂色只会影响一行一列,所以可以设 dp(i,j)dp(i,j) 表示还需要涂 ii 行 , jj 列的期望步数。

1.涂色格所在行列均未染色,由 dp(i1,j1)dp(i-1,j-1) 转移,概率为 in×jn\frac{i}{n} \times \frac{j}{n}

阅读全文 »

P3911 最小公倍数之和

简单问题复杂化是解决问题的一个好方法。

cic_i 表示 ii 出现的次数,nn 为最大数字。

i=1nj=1nci×cj×lcm(i,j)\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times lcm(i,j)

阅读全文 »

P6156 简单题

i=1nj=1n(i+j)kf(gcd(i,j))gcd(i,j)\sum_{i=1}^n \sum_{j=1}^n (i+j)^k f(\gcd(i,j)) \gcd(i,j)

显然 f(i)=μ2(i)f(i)=\mu^2(i)

阅读全文 »

P4619 [SDOI2018]旧试题

i=1Aj=1Bk=1Cd(ijk)\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)

i=1Aj=1Bk=1Cxiyjzk[(x,y)=1][(y,z)=1][(x,z)=1]\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{x|i}\sum_{y|j}\sum_{z|k}[(x,y)=1][(y,z)=1][(x,z)=1]

阅读全文 »

P1587 [NOI2016]循环之美

类比十进制下的纯循环小数,kk 进制下的纯循环小数满足最简分数分母与 kk 互质。

而题目要求相同数值只计数一次,所以只需要考虑最简分数的情况。

那么答案为:

阅读全文 »